
public class mergeSort{

	/**
	 *归并排序的操作步骤：
	 *申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
	 *设定两个指针，最初位置分别为两个已经排序序列的起始位置
	 *比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
	 *重复步骤3直到某一指针到达序列尾
	 *将另一序列剩下的所有元素直接复制到合并序列尾
	 *
	 *
	 *分类：内部比较排序
	 *数据结构：数组
	 *最差时间复杂度和最优时间复杂度都是： O(nlogn)
	 *平均时间复杂度： O(nlogn)
	 *所需辅助空间： O(n)
	 *稳定性：稳定
	 * 
	 * [sort description]
	 * @param array [description]
	 */
	public void sort(int [] array){
		MSort(array,0,array.length-1);
	}

	/**
	 * [MSort description]
	 * @param array [description]
	 * @param left  [description]
	 * @param right [description]
	 */
	private void MSort(int [] array, int left, int right){
		if(left == right){
			return;
		}
		int mid = (right+left) / 2;
		MSort(array,left,mid);
		MSort(array,mid+1,right);
		merge(array,left,mid,right);
	}

	private void merge(int [] array,int left,int mid, int right){
		int len = right - left + 1;
		int [] temp = new int [len]; // 辅助空间为O(n)
		int index = 0;
		int i,j;
		for (i=0,j=mid+1; i<=mid && j <= right;) {
			if (array[i] >= array[j]) {
				temp[index++] = array[j++]; 
			}else{
				temp[index++] = array[i++];
			}
		}
		while(i <= mid){
			temp[index++] = array[i++];
		}
		while(j <= right){
			temp[index++] = array[j++];
		}
		for (int k=0; k<len; k++) {
			array[k] = temp[k];
		}
	}
}